package com.leetcode.dynamic_programming.bag;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author Dennis Li
 * @date 2020/10/13 22:45
 */
// 多重背包问题
public class MultiBags {

    private static final Scanner scanner = new Scanner(System.in);

    public static void multiBags1(){
        int n = scanner.nextInt(), m = scanner.nextInt();
        int[] dp = new int[m + 1];

        for (int i = 0; i < n; i++) {
            int v = scanner.nextInt(), w = scanner.nextInt(), s = scanner.nextInt();
            for (int j = m; j >= 0; j--) {
                // 限制次数的情况下，就添加一重循环
                for (int k = 1; k <= s && k * v <= j; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * v] + k * w);
                }
            }
        }

    }

    // 二进制拆解优化
    public static void multiBags2() {

        class Good {
            int v, w;
            public Good(int v, int w) {
                this.v = v;
                this.w = w;
            }
        }

        int n = scanner.nextInt(), m = scanner.nextInt();
        int[] dp = new int[m + 1];
        List<Good> goods = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int v = scanner.nextInt(), w = scanner.nextInt(), s = scanner.nextInt();
            // 转换成含有重复值的0-1背包问题，并且将数s转换为二进制表示方法
            for (int j = 1; j <= s; j *= 2) {
                s -= j;
                // 比如数7
                // 由于在0-1背包中存在选与不选的情况
                // 将7拆成1 2 4可以取 0 ~ 7的所有数
                // 0 -- 代表0-1背包都不选
                // 1 -- 代表0-1背包只选1
                // 2 -- 代表0-1背包只选2
                // 3 -- 代表0-1背包选1和2
                // 4 -- 代表0-1背包只选4
                // 5 -- 代表0-1背包选择1和4
                // ... （其他同理）
                goods.add(new Good(v * j, w * s));
            }
            if (s > 0)
                // 当S没按二进制取完的时候，加入剩下的s
                goods.add(new Good(v * s, w * s));
        }

        for (Good good : goods) {
            for (int i = m; i >= good.v; i--) {
                dp[i] = Math.max(dp[i], dp[i - good.v] + good.w);
            }
        }

        System.out.println(dp[m]);
    }

    // 采用单调队列的优化版本
    public static void multiBags3() {

    }

}
